package com.leo.m1802.d25;

import java.util.Arrays;

/**
 * Created by LEO on 2018/2/25.
 */
public class Sort {
    /**
     * 简单插入排序
     * @param a
     */
    public void simpleInsert(int[] a){
        for (int i = 1; i < a.length; i++) {
            for (int j = i; j >0 ; j--) {
                if (a[j] < a[j-1]){
                    swap(a, j, j-1);
                }else {
                    break;
                }
            }
        }
    }

    /**
     * 希尔排序
     * @param a
     */
    public void shellSort(int[] a){
        int gap = a.length/2;
        int j;
        for (;gap>0;gap/=2) {
            for (int i = 0; i < gap; i++) {
                j = i + gap;
                while (j < a.length) {
                    int temp = j;
                    while (temp - gap >= 0 && a[temp] < a[temp - gap]) {
                        swap(a, temp, temp - gap);
                        temp -= gap;
                    }
                    j += gap;
                }
            }
        }
    }


    public void swap(int[] a, int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    /**
     * 简单选择排序
     * @param a
     */
    public void simpleChoose(int[] a){
        for (int i = 0; i < a.length - 1; i++) {
            int min = i;
            for (int j = i+1; j < a.length; j++) {
                if (a[j] < a[min]) { min = j; }
            }
            swap(a, i, min);
        }
    }

    /**
     * 堆排序
     * 按照从小到大排序，所以我们建大顶堆
     * @param a
     */
    public void heapSort(int[] a){
        for (int i = a.length/2; i >=0 ; i--) {
            heapAdjust(a,a.length, i);
        }
        for (int i = a.length-1; i > 0 ; i--) {
            swap(a, 0, i);
            heapAdjust(a, i, 0);
        }
    }

    /**
     * 堆调整
     * @param a   堆
     * @param len 调整长度
     * @param n   调整的点
     */
    private void heapAdjust(int[] a, int len,int n){
        while (n<len){
            int max = 0;
            if (2*n+1<len && a[2*n+1] > a[n]) { max=1; }
            if (2*n+2<len && a[2*n+2] > a[n] && a[2*n+2] > a[2*n+1]) { max = 2; }
            if (max > 0){
                swap(a, n, 2*n+max);
                n = 2*n+max;
            }else {
                break;
            }
        }
    }

    /**
     * 冒泡排序
     * @param a
     */
    public void bubbleSort(int[] a){
        for (int i = a.length; i > 0; i--) {
            for (int j = 0; j < i-1 ; j++) {
                if (a[j] > a[j+1]){ swap(a, j, j+1); }
            }
        }
    }

    public void quickSort(int[] a){
        quickSort01(a, 0, a.length-1);
    }

    private void quickSort01(int[] a, int begin, int end){
        if (begin < end){
            int pos = partition(a, begin, end);
            quickSort01(a, begin, pos-1);
            quickSort01(a, pos+1, end);
        }
    }

    private int partition(int[] a, int i, int j){
        int temp = a[i];
        while (i<j){
            while (i<j && a[j]>=temp) {j--;}
            a[i] = a[j];
            while (i<j && a[i]<=temp) {i++;}
            a[j] = a[i];
        }
        a[i] = temp;
        return i;
    }

    /**
     * 归并排序
     * @param a
     */
    public void mergeSort(int[] a){
        mergeSort1(a, 0, a.length-1);
    }

    public void mergeSort1(int[] a, int begin, int end){
        if (begin < end){
            int len = (end-begin)/2;
            mergeSort1(a, begin, begin+len);
            mergeSort1(a, begin+len+1, end);
            merge(a, begin, begin+len, end);
        }
    }

    public void merge(int[] a, int m, int mend, int n){
        int[] temp = new int[n-m+1];
        int i = m,j = mend+1,k=0;
        while (i<=mend && j<=n){
            if (a[i] < a[j]){
                temp[k++] = a[i++];
            }else {
                temp[k++] = a[j++];
            }
        }
        while (i<=mend){temp[k++] = a[i++];}
        while (j<=n){temp[k++] = a[j++];}

        for (int l = 0; l < temp.length; l++) {
            a[m+l] = temp[l];

        }
    }

    /**
     * 基数排序
     * @param a
     */
    public void radixSort(int[] a){

    }

    public static void main(String[] args) {
        Sort s = new Sort();
        int[] a = new int[]{5,73,723,24,3,3,13,3,84,856,236,3,0,-2,23,-3,23,54,3};
//        s.simpleInsert(a);
//        s.shellSort(a);
//        s.simpleChoose(a);
//        s.heapSort(a);
//        s.bubbleSort(a);
//        s.quickSort(a);
        s.mergeSort(a);
        System.out.println(Arrays.toString(a));
    }
}
